public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();

    }

    public int numberOfArithmeticSlices(int[] nums) {
        /**
         * 等差数列划分
         * 状态表示：
         *  dp[i]表示以下标元素为结尾的所有子数组中，等差子数组的个数
         * 状态转移方程：
         *  if(nums[i]-nums[j] == nums[j]-nums[k]) {
         *      dp[i] = 1 + dp[i-1];
         *  }
         * 初始化：
         *  由状态转移方程可知，在为i下标元素填表时，需要使用到i-1 和 i-2的元素
         *  因此为了避免发生数组越界访问的情况，从下标2开始填表，dp[0] = dp[1] = 0;
         * 填表顺序：
         *  从左到右
         * 返回值：
         *  返回dp表之和
         * */
        // 1 预处理
        int n = nums.length;
        if(n < 3) return 0;
        // 2 创建dp表
        int[] dp = new int[n];
        // 3 初始化
        // 4 填表
        int ret = 0;
        for(int i = 2; i < n; i++) {
            if(nums[i]-nums[i-1] == nums[i-1]-nums[i-2]) {
                dp[i] = 1 + dp[i-1];
                ret += dp[i];
            }
        }
        // 5 返回值
        return ret;
    }
}
